package algorithm;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * GenerateParentheses
 *
 * @author nanxin.chen
 * @date 2015/10/22
 */
public class GenerateParentheses {
    public void generate(List<String> rsList, int n, String s) {
        if (n == 0) {
            /*rsList.add("()" + s);
            rsList.add(s + "()");
            rsList.add("(" + s + ")");*/
            rsList.add(s);
        }else {
            generate(rsList, n - 1, "()" + s);
            generate(rsList, n - 1, s + "()");
            generate(rsList, n - 1, "(" + s + ")");
        }
    }

    public static void generateWithRepeat() {
        GenerateParentheses gp = new GenerateParentheses();
        Map<String, Integer> cMap = new HashMap<>();
        List<String> rsList = new ArrayList<>();
        gp.generate(rsList, 3 , "");
        System.out.println("size:" + rsList.size());
        for (String s : rsList) {
            if (cMap.get(s) == null) {
                cMap.put(s, 1);
            }else {
                cMap.put(s, cMap.get(s) + 1);
            }
            System.out.println(s);
        }

        System.out.println("map size:" + cMap.size());
        for (Map.Entry<String, Integer> e : cMap.entrySet()) {
            System.out.println(e.getKey() + "\t" + e.getValue());
        }
    }

    public static void main(String[] args) {
        generateWithRepeat();

    }
}
